The present invention relates to packet-based communication systems. More particularly, and not by way of limitation, the present invention is directed to a Content Addressable Memory (CAM) and method of downloading and banking filters in the CAM.
CAMs are very commonly used in network devices to perform multi-field classification/searching on packet header fields. A CAM stores a number of filters, and the first filter that matches the fields in the packet header is returned as a match. Generally, there are different types/groups of filters that are stored in the CAM based on the application for which each filter type is used. For example, one filter group may be used for tunnels, another group may be used for differentiated services (diffserv), another group for firewall, and the like. A search is usually done for multiple filter groups depending upon the type of packet and the results of previous filter lookups on the packet.
To reduce the number of lookups needed in the CAM for each packet, filters within a filter-group are usually “flattened”, where user-defined filters (which could require multiple lookups in the CAM for each packet) are optimally combined to form the CAM filters that are actually installed in the CAM for packet searches. This process of flattening results in an increase in the number of filters to be installed in the CAM, but ensures that each packet will require only one lookup for a particular filter group (i.e., only one CAM lookup for each application), instead of multiple CAM lookups, as would be required per group if the filters were not flattened.
Whenever there is a change in user-defined policy that requires a change in filters for a particular application/filter-group, the filters for that particular group have to be flattened again. This may generate a completely new set of filters for that filter-group. Therefore, this new set of filters is downloaded to the CAM in a separate bank for the new filter-group, while the old filters are still being used for lookup. After the download process is completed, the banks for the given filter-group are switched so that the newly downloaded filters become active and the old bank, that has now become inactive, is free for use for the next download operation for the filter-group. Thus, essentially two banks are maintained for each filter-group: one bank that is active and is being used for doing lookups, and one bank that is reserved for downloading new filters. Additionally, since the number of filters in different filter-groups can vary widely (depending upon the characteristics requirements of the product for different applications), the inactive banks for different filter-groups cannot be shared even though only one bank is being downloaded at a time. Once the inactive bank is made active, the new spare bank that was earlier being used for one filter-group may not be big enough for the next filter-group that needs an update.
Thus, a major problem with the existing filter-bank implementation is that it requires double the needed CAM space for bank management. This wastes valuable CAM memory that is usually expensive and power-hungry. Also, it is not possible to use the CAM in a completely shared mode where filters not being used by one application can be utilized by another application.
A known approach that solves some of the problems of the existing filter-bank implementation is to make all filter-groups the same size. This allows the spare bank to be shared among all filter-groups, thus removing the need for a separate spare bank for each and every filter-group. However, this approach is still inefficient because it allocates the same amount of CAM space to an application requiring only a small number of filters as it allocates to an application requiring a large number of filters. For example, if a product needs to support up to 256 tunnels and up to 4K diffserv filters for Quality of Service (QoS) provisioning, the filter-group used for tunneling would be allocated as much CAM space as the filter-group used for diffserv, thereby wasting 16 times more CAM space than needed for tunnels. Thus, this approach works well only if the different applications require approximately the same amount of CAM space, thus reducing the amount of wasted CAM memory. However, this approach still does not allow the entire CAM to be used in a completely dynamically shared mode in which any application can use the filters not being used by another application. For example, this approach does not enable a user to install more than 256 tunnels in a CAM that has far less than 4 k diffserv filters configured.